class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def constructFromPrePost(self, preorder, postorder):
        """
        :type preorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        node = TreeNode(preorder[0])
        if len(preorder) == 1:
            return node
        if preorder[1] == postorder[-2]:
            node.left = self.constructFromPrePost(preorder[1:], postorder[:-1])
        else:
            index1 = 0
            while postorder[index1] != preorder[1]:
                index1 += 1
            index2 = 1
            while preorder[index2] != postorder[-2]:
                index2 += 1
            node.left = self.constructFromPrePost(preorder[1: index2], postorder[: index1 + 1])
            node.right = self.constructFromPrePost(preorder[index2:], postorder[index1 + 1: -1])
        return node


